//方法2
//递归法



#include<iostream>
using namespace std;

//Definition for singly-linked list.
  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };
 
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
           if(head==NULL||head->next==NULL)
           {
               return head;
           }
           ListNode* newnode=reverseList(head->next);
           head->next->next=head;
           head->next=NULL;
           return newnode;
    }
};